Propositional Logic

Propositional logic is a branch of logic that deals with propositions. A proposition is a statement that is either true or false. Propositional logic is also called sentential logic or statement logic. Propositional logic is the simplest form of logic and is used to study the internal structure of propositions. In this section, propositional logic is studied in a formal way. First a formal system is defined and then the syntax and different semantics of propositional logic are studied.

Syntax

Propositions are statements that are either true or false. Formal propositional logic is a branch of logic that deals with only propositions in a formal way. To study a subject formally, it is necessary to represent the subject in a symbolic form. For this reason, an alphabet and a formula are defined. An alphabet is a set of symbols that are used to build formulas. A formula (sentence) is a string of symbols from the alphabet that represents a proposition.

Propositions may be constituted by using natural language, but natural language is not precise enough to represent propositions formally. For this reason, in propositional logic, the internal structure of propositions is not considered instead each proposition is considered as a whole entity. Propositions are represented by symbols such as $P_1$, $P_2$, $P_3$, etc. These symbols are called propositional variables, atomic propositions, or prime formulas.

To study more complicated propositions, it is necessary to be able to build more complex propositions from simpler ones. This is done by using logical connectives. Logical connectives are symbols that are used to combine propositions to form more complex propositions. The most common logical connectives are:

• Negation ($\neg P$)
• Conjunction ($P\wedge Q$)
• Disjunction ($P\vee Q$)
• Implication ($P⟹Q$)
• Biconditional ($P⟺Q$)

The sentences formed by using logical connectives are called compound propositions or compound formulas.

The alphabet of propositional logic is defined as follows;

$$A=\{\neg ,(,),\wedge ,\vee ,⟹,⟺,P_0,P_1,\dots \}$$

A well-formed formula (wff) of propositional logic;

1. An atomic formula is a well-formed formula. (e.g. $P_0$, $P_1$, $\dots$)
2. If $\varphi$ is a well-formed formula, then $\neg \varphi$ is a well-formed formula.
3. If $\varphi$ and $\psi$ are well-formed formulas, then $(\varphi \wedge \psi )$, $(\varphi \vee \psi )$, $(\varphi ⟹\psi )$, and $(\varphi ⟺\psi )$ are well-formed formulas.

TODO: Omiting the parentheses.

Truth Semantics

Well-formed formulas does not have any meaning by themselves. They are just valid and meaningful strings of symbols. For example $P_0\wedge P_1$ is a well-formed formula but it does not have any meaning by itself. To give meaning to it, it is necessary to define;

1. The derivation rules for the truth values of compound propositions.
2. The truth values of atomic propositions.

Truth semantics of propositional logic is defined by using truth tables. A truth table is a table that shows the truth values of a compound proposition for all possible truth values.

Proof Semantics

Soundness and Completeness

References

• Kleene, S. C. (1967). Mathematical logic. Dover Publications.